1854E - Game Bundles - CodeForces Solution

#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    const int N = 60;
    ll m;
    cin >> m;
    // mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
    // m = gen() % ll(9e9) + 1e9;
    for (int kek2 = 0; kek2 < 30; kek2++)
        for (int kek = 0; kek + kek2 * 2 < 60; kek++) {
            vector<ll> dp(N + 1);
            dp[0] = 1;
            map<int, int> cnt;
            cnt[1] = kek;
            cnt[2] = kek2;
            vector<int> starters;
            for (auto [x, y] : cnt) {
                for (int i = 0; i < y; i++)
                    starters.push_back(x);
            }
            for (auto elem : starters) {
                for (int val = N; val >= elem; val--) {
                    dp[val] += dp[val - elem];
                }
            }

            vector<ll> elems;
            map<ll, int> id;
            for (int val = 0; val < 30 && dp[val] > 0; val++) {
                elems.push_back(dp[val]);
                id[dp[val]] = val;
            }
            sort(elems.rbegin(), elems.rend());
            int sz = N - kek;
            vector<set<ll>> rem(sz + 1);
            vector<map<ll, pair<ll, ll>>> delta(sz + 1);
            rem[0].insert(m);
            const int LIM = 1e3;
            for (auto elem : elems) {
                auto nxt = rem;
                for (int used = 0; used < sz; used++)
                    for (auto val : rem[used])
                        if (val - (sz - used) * elem <= 0)
                            for (int add = 1; add <= min<ll>(sz - used, val / elem); add++) {
                                nxt[used + add].insert(val - add * elem);
                                delta[used + add][val - add * elem] = {elem, add};
                            }
                rem = std::move(nxt);
                for (int used = 0; used < sz; used++) {
                    while (rem[used].size() > LIM)
                        rem[used].erase(prev(rem[used].end()));
                }
            }

            ll cur = 0;
            int steps = -1;
            for (int i = 0; i <= sz; i++)
                if (!rem[i].empty() && *rem[i].begin() == 0) {
                    steps = i;
                    break;
                }
            if (steps != -1) {
                while (cur < m) {
                    assert(delta[steps].count(cur));
                    auto &[elem, add] = delta[steps][cur];
                    for (int i = 0; i < add; i++)
                        starters.push_back(60 - id[elem]);
                    cur += elem * add;
                    steps -= add;
                }
                cout << starters.size() << '\n';
                for (auto elem : starters)
                    cout << elem << ' ';
                cout << '\n';
                return;
            }
        }
    assert(false);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        solve();
    }
    return 0;
}